/**
 * Created by forcht on 2018/4/30.
 */
public class Solution {
    //    public int maxSubArray(int[] A) {
//        int[] dp=new int[A.length];
//        dp[0]=A[0];
//        int max=dp[0];
//        for(int i=1;i<A.length;i++){
//            dp[i]=Math.max(dp[i-1]+A[i],A[i]);
//            if(dp[i]>max)max=dp[i];
//        }
//        return max;
//    }
    public int maxSubArray(int[] A) {
        if (A.length == 0) return 0;
        int sum = 0, max = A[0];
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            if (max < sum) max = sum;
            if (sum < 0) sum = 0;
        }
        return max;
    }

    public static void main(String[] args) {
        int[] a={-5,-3,-5,-6,-7};
        System.out.println(new Solution().maxSubArray(a));
    }
}
